package com.example.algorithm.dynamicprogramming;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;

/**
 * 如果序列 X_1, X_2, ..., X_n 满足下列条件，就说它是 斐波那契式 的：
 * n >= 3
 * 对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}
 * 给定一个严格递增的正整数数组形成序列，找到 A 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。
 * <p>
 * （回想一下，子序列是从原序列 A 中派生出来的，它从 A 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。
 * 例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）
 * <p>
 * 示例 1：
 * <p>
 * 输入: [1,2,3,4,5,6,7,8]
 * 输出: 5
 * 解释:
 * 最长的斐波那契式子序列为：[1,2,3,5,8] 。
 * <p>
 * 示例 2：
 * 输入: [1,3,7,11,12,14,18]
 * 输出: 3
 * 解释:
 * 最长的斐波那契式子序列有：
 * [1,11,12]，[3,11,14] 以及 [7,11,18] 。
 * <p>
 * 提示：
 * 3 <= A.length <= 1000
 * 1 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9
 */
public class Leetcode873_LenLongestFibSubseq {
    public static void main(String[] args) {
        int[] nums = {1,3,4,7,10,11,12,18,23,35};
        System.out.println(new Solution().lenLongestFibSubseq(nums));

    }

    static class Solution {
        /**
         * 动态规划
         *
         * 思路:
         * 每一个起始对都要遍历后面的数组剩余的元素能否记录状态?,用以不用重复遍历
         *
         * 将斐波那契子序列中的两个连续项A[i], A[ j] 视为单结点(i, j)，整个子序列是这些连续结点之间的路径
         * 例如A[1,2,3,4,5,6,7,8.9,11,13]
         * 对于斐波那契式的子序列(A[1] = 2, A[2] = 3, A[4] = 5, A[7] = 8, A[10] =13)，结点之间的路径为
         * (1, 2) <-> (2, 4) <-> (4, 7) <-> (7, 10)
         * 可得:只有当A[i] + A[j] = A[k]时(i,j) (j,k)才是连通的(i,j,k均是指数组下标)
         *
         * 原问题与子问题:
         *    1.子问题:求解(i,j)为  结尾  的fib子序列的长度
         *
         *    2.设计状态:dp(i,j)表示(i,j)结尾的fib子序列的长度
         *
         *    3.状态转移方程:
         *       if ((A[i] + A[j] )== A[k])
         *          dp(j,k) = dp(i,j) + 1
         *       目标值 = max(dp(i,j))
         *    4.边界值: dp(i,j) = 2(fib子序列最短也会有两个)
         *
         *
         * @param arr
         * @return
         */
        public int lenLongestFibSubseq2(int[] arr) {
            Map<Integer, Integer> arrIndexMap = new HashMap<>(); // 方便快速查找数组元素对应的索引值
            for (int i = 0; i < arr.length; i++) {
                arrIndexMap.put(arr[i], i);
            }
            int size = arr.length;

            // key: (i,j), value: 以(i,j)为  结尾 的fib子序列的长度 即dp(i,j)
            // 之所以能用一个int表示(i,j)是因为i,j都不相同(i < j)那么 [i * n + j (n为数组长度或者更大的数,不然可能会冲突)]一定唯一(二维变一维小技巧)
            Map<Integer, Integer> subFibLengthMap = new HashMap<>();
            int res = 0;
            // 倒着进行判断更加方便 即if (A[i] == A[k] - A[j]) 则可得 dp(j,k) = dp(i,j) + 1
            for (int k = 0; k < arr.length; ++k) {
                for (int j = 0; j < k; ++j) {
                    int i = arrIndexMap.getOrDefault(arr[k] - arr[j], -1);
                    if (i >= 0 && i < j) { // 说明能在j前面找到一个i 使得(A[i] == A[k] - A[j])
                        // 根据 dp(i,j) 来更新 dp(j,k) 的值
                        int dpIJ = subFibLengthMap.getOrDefault(i * size + j, 2);
                        int dpJK = dpIJ + 1;
                        subFibLengthMap.put(j * size + k, dpJK);
                        res = Math.max(res, dpJK);
                    }
                }
            }
            return res > 2 ? res : 0;
        }

        /**
         * 解法一:暴力法
         * 先依次从数组中找两个元素充当菲波那切数列的前两项，然后向后遍历寻找是否有满足当前菲波那切数列的元素，有的话就更新最大长度值
         *
         * @param arr
         * @return
         */
        public int lenLongestFibSubseq1(int[] arr) {
            Set<Integer> numSet = Arrays.stream(arr).boxed().collect(Collectors.toSet());
            int res = 0;

            for (int i = 0; i < arr.length; i++) {
                for (int j = i + 1; j < arr.length; j++) {
                    // x,y用于存储fib数列的最后两项
                    int x = arr[j];
                    int y = arr[i] + arr[j];
                    int len = 2;

                    while (numSet.contains(y)) {
                        ++len;
                        int tmp = y;
                        y = x + y;
                        x = tmp;
                    }
                    res = Math.max(res, len); // 查找一个可能的fib数列,最后更新fib子序列的最大长度值
                }
            }

            return res > 2 ? res : 0;

        }

        public int lenLongestFibSubseq(int[] arr) {
            return lenLongestFibSubseq2(arr);
        }
    }
}
